#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

//利用滚动数组进行空间优化
//只需要一维的dp表就可以解决问题
//如果不采用空间优化
    //dp[i][j] - dp[i - 1][j] / dp[i][j] = dp[i - 1][j - wi] + vi
//可见，填写本行的dp表时，只与上一行有关，则可以将dp表优化到两行
//如果要将空间优化到一行d表，那么就可以将上一行的数据当作基础，从右往左遍历（如果从左往右，就会覆盖掉上一行的dp[i - 1][j - wi]）填写dp表即可

int main() {
    int n, v;
    cin >> n >> v;
    vector<vector<int>> items(n, vector<int>(2, 0));
    for (auto & item : items)
        cin >> item[0] >> item[1];

    vector<int> dp(v + 1, 0);

    //填表
    for (int i = 1; i < n + 1; i++)
        for (int j = v; j >= items[i - 1][0]; j--)
                dp[j] = ::max(dp[j], dp[j - items[i - 1][0]] + items[i - 1][1]);

    cout << dp[v] << endl;

    //第二问
    dp = vector<int>(v + 1, -1);
    dp[0] = 0;

    //填表
    for (int i = 1; i < n + 1; i++)
        for (int j = v; j >= items[i - 1][0]; j--)
            if (dp[j - items[i - 1][0]] != -1)
                dp[j] = ::max(dp[j], dp[j - items[i - 1][0]] + items[i - 1][1]);

    if (dp[v] == -1)
        cout << 0 << endl;
    else
        cout << dp[v] << endl;

    return 0;
}


// #include <iostream>
// #include <vector>
// #include <cmath>
// using namespace std;

// int main() {
//     int n, v;
//     cin >> n >> v;
//     vector<vector<int>> items(n, vector<int>(2, 0));
//     for (auto & item : items)
//         cin >> item[0] >> item[1];

//     //第一问：背包不满
//     //dp[i][j]表示：考虑前i个物品，体积小于等于j时的最大价值
//     //如果第i个物品不取，dp[i][j] = dp[i - 1][j]
//     //如果取第i个物品，dp[i][j] = wi + dp[i - 1][j - vi]

//     //关于dp表的初始化
//     //由于多了一行一列，因此物品从下标1开始算
//     //dp表第一行，即物品0体积小于等于j的最大价值，由于物品0体积为0，价值为0，因此第一行初始化为0
//     //dp表第一列，即体积小于等于0的最大价值，由于每隔物品的体积至少为1，因此第一列初始化为0
//     vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));

//     //填表
//     for (int i = 1; i < n + 1; i++)
//     {
//         for (int j = 1; j < v + 1; j++)
//         {
//             if (j - items[i - 1][0] >= 0)
//                 dp[i][j] = ::max(dp[i - 1][j], dp[i - 1][j - items[i - 1][0]] + items[i - 1][1]);
//             else
//                 dp[i][j] = dp[i - 1][j];
//         }
//     }

//     cout << dp[n][v] << endl;

//     //第二问：背包必须装满
//     //dp[i][j]表示：考虑前i个物品，体积等于j时的最大价值
//     //约定：如果 考虑前i个物品，没有满足体积等于j的情况，则dp[i][j] = -1
//     //如果第i个物品不取，dp[i][j] = dp[i - 1][j] 
//         //(如果dp[i - 1][j] = -1，那么第i个物品不拿也一定不能满足体积等于j，因此dp[i][j] = dp[i][j - 1])
//     //如果取第i个物品，
//         //如果 j - vi >= 0 && dp[i - 1][j - vi] != -1
//         //则dp[i][j] = wi + dp[i - 1][j - vi]

//     dp = vector<vector<int>>(n + 1, vector<int>(v + 1, 0));
//     //关于dp表的初始化
//     //由于多了一行一列，因此物品从下标1开始算
//     //dp表第一行，即物品0 体积等于j的最大价值，由于物品0体积为0，价值为0，因此
//         //dp[0][0] = 0，第一行其余的位置初始化为-1
//     //dp表第一列，即体积等于0的最大价值，由于每隔物品的体积至少为1，不拿所有物品，因此第一列初始化为0
//     for (int i = 1; i < v + 1; i++)
//         dp[0][i] = -1;

//     //填表
//     for (int i = 1; i < n + 1; i++)
//     {
//         for (int j = 1; j < v + 1; j++)
//         {
//             if (j - items[i - 1][0] >= 0 && dp[i - 1][j - items[i - 1][0]] != -1)
//                 dp[i][j] = ::max(dp[i - 1][j], dp[i - 1][j - items[i - 1][0]] + items[i - 1][1]);
//             else
//                 dp[i][j] = dp[i - 1][j];
//         }
//     }

//     if (dp[n][v] == -1)
//         cout << 0 << endl;
//     else
//         cout << dp[n][v] << endl;

//     return 0;
// }
// 64 位输出请用 printf("%lld")